package tree.threadedbinarytree;

import java.util.Scanner;

/**
 * 线索二叉树
 */
public class ThreadBinTree {
    private TBinTreeNode root;
    private TBinTreeNode pre;
    private TBinTreeNode head;

    public ThreadBinTree() {
        this.setRoot(null);
        head = new TBinTreeNode(null, false, false);
        pre = null;
    }

    /**
     * 创建线索二叉树
     */
    public void createThrBinTree() {
        this.setRoot(createSubTree());
        head.settLeftChild(this.getRoot());
        inThreading(this.getRoot());
        addHead();
    }

    /**
     * 创建二叉树
     *
     * @return
     */
    private TBinTreeNode createSubTree() {
        TBinTreeNode subTree = null;
        String s = new Scanner(System.in).next();

        if (!("#".equals(s))) {
            subTree = new TBinTreeNode(s, false, false);
            subTree.settLeftChild(createSubTree());
            subTree.settRightChild(createSubTree());
        }
        return subTree;
    }

    /**
     * 二叉树线索化
     *
     * @param root 二叉树的根节点
     */
    private void inThreading(TBinTreeNode root) {
        if (root == null) {
            return;
        }

        inThreading(root.gettLeftChild());
        if (root.gettLeftChild() == null) {
            root.setLeftThread(true);
            root.settLeftChild(pre);
        }
        if (pre != null && pre.gettRightChild() == null) {
            pre.setRightThread(true);
            pre.settRightChild(root);
        }
        pre = root;
        inThreading(root.gettRightChild());
    }

    /**
     * 添加头节点
     */
    private void addHead() {
        TBinTreeNode p = this.getRoot();
        // 找到最左节点，该节点的左节点指向头节点
        while (p.gettLeftChild() != null) {
            p = p.gettLeftChild();
        }
        p.setLeftThread(true);
        p.settLeftChild(this.getHead());
        // 线索化的最后一个节点，该节点指向头节点，同时头节点的右节点指向该节点
        pre.setRightThread(true);
        pre.settRightChild(this.getHead());
        this.getHead().setRightThread(true);
        this.getHead().settRightChild(pre);
        pre = null;
    }

    /**
     * 中序遍历线索二叉树
     *
     * @param head 线索二叉树的头节点
     */
    public void inOrderTraverse(TBinTreeNode head) {
        TBinTreeNode p = head.gettLeftChild();

        while (p != head) {
            while (p.gettLeftChild() != null && !p.isLeftThread()) {
                p = p.gettLeftChild();
            }
            System.out.println(p.getData());
            while (p.gettRightChild() != null && p.isRightThread() && p.gettRightChild() != head) {
                p = p.gettRightChild();
                System.out.println(p.getData());
            }
            p = p.gettRightChild();
        }
    }

    public TBinTreeNode getRoot() {
        return root;
    }

    private void setRoot(TBinTreeNode root) {
        this.root = root;
    }

    public TBinTreeNode getHead() {
        return head;
    }
}